import com.sun.xml.internal.bind.v2.model.core.ID;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * Created by L.jp
 * Description://对于这种上下级关系，一个下属最多可以有一个上级，但是一个上级可以有多个下属，而每一个员工存储了不同的信息，这种对应关系形成了树的结构
 *         // 所以优先使用树的思想来解决问题，按照目前我说学过的知识不能很好的解决，所以通过了解发现用Map解决问题最方便
 * User: 86189
 * Date: 2021-10-17
 * Time: 10:28
 */
class Employee {
    public int id;
    public int importance;
    public List<Integer> subordinates;
}
public class Staff {
    //建立Map哈希表存储员工id和每个员工的信息
    Map<Integer, Employee> map = new HashMap<Integer, Employee>();
    public int getImportance(List<Employee> employees, int id) {
        for (Employee employee1 : employees) {
            map.put(employee1.id,employee1);
        }
        //返回员工的重要度之和
        return (dfs(id));
    }
    //深度优先搜索
    public int dfs(int id){
        //通过map get找到每个员工
        Employee employee=map.get(id);
        int ret=employee.importance;
        //每个员工的下属集合是一个list
        List<Integer> subordinate= employee.subordinates;
        for (int i:subordinate) {
            ret+=dfs(i);//通过list巧妙利用for循环递归每个子树，i就是list的元素即下属的id
        }
        return ret;
    }
}
